import random
import math
from collections import Counter

class KNN:
    def __init__(self, k=3):
        if k <= 0:
            raise ValueError("K must be a positive integer.")
        self.k = k
        self.x_train = None
        self.y_train = None

    def _euclidean_distance(self, p1, p2):
        return math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))

    def fit(self, x_train, y_train):
        if len(x_train) != len(y_train):
            raise ValueError("训练数据和标签的长度必须相同。")
        self.x_train = x_train
        self.y_train = y_train
        print(f"模型已训练，训练集大小: {len(self.x_train)}")

    def _get_knn_indices(self, test_point):
        distances = [self._euclidean_distance(test_point, train_point) for train_point in self.x_train]
        sorted_indices = sorted(range(len(distances)), key=lambda i: distances[i])

        return sorted_indices[:self.k]

    def _get_label(self, test_point):
        knn_indices = self._get_knn_indices(test_point)
        neighbor_labels = [self.y_train[i] for i in knn_indices]
        most_common_label = Counter(neighbor_labels).most_common(1)[0][0]
        return most_common_label

    def predict(self, x_test):
        if not self.x_train or not self.y_train:
            raise RuntimeError("模型尚未训练，请先调用fit方法。")

        predicted_labels = [self._get_label(point) for point in x_test]
        return predicted_labels


if __name__ == "__main__":
    train_data = [
        [158, 50], [160, 52], [165, 55], [168, 58],
        [170, 65], [172, 68], [175, 70], [178, 75],
        [180, 85], [182, 88], [185, 90], [188, 95]
    ]
    train_labels = ['瘦', '瘦', '瘦', '瘦', '正常', '正常', '正常', '正常', '胖', '胖', '胖', '胖']

    test_points = [
        [162, 53],
        [174, 72],
        [183, 92]
    ]

    print("--- 使用 K=3 进行预测 ---")
    knn_classifier = KNN(k=3)
    knn_classifier.fit(train_data, train_labels)
    predictions = knn_classifier.predict(test_points)

    for i, point in enumerate(test_points):
        print(f"测试点 {i + 1}: 特征={point} -> 预测结果: '{predictions[i]}'")

    print("\n--- 评估不同K值的效果 ---")
    random.seed(0)
    all_indices = list(range(len(train_data)))
    random.shuffle(all_indices)
    eval_split = int(len(train_data) * 0.7)

    eval_x_train = [train_data[i] for i in all_indices[:eval_split]]
    eval_y_train = [train_labels[i] for i in all_indices[:eval_split]]
    eval_x_test = [train_data[i] for i in all_indices[eval_split:]]
    eval_y_test = [train_labels[i] for i in all_indices[eval_split:]]

    for k in range(1, 6):
        knn_eval = KNN(k=k)
        knn_eval.fit(eval_x_train, eval_y_train)
        eval_predictions = knn_eval.predict(eval_x_test)

        correct = sum(1 for true, pred in zip(eval_y_test, eval_predictions) if true == pred)
        accuracy = correct / len(eval_y_test)
        print(f'K的取值为 {k}, 预测准确率为 {accuracy * 100:.1f}%')
